#include "table.h"

/**
 * 二分插入排序
 * @param {table} *tab          待排序表
 * @return {void}
 */
void binarysort(table *tab) {
    int i, j, low, high, mid;
    // 从第二个元素开始，依次插入
    for (i = 2; i <= tab->length; i++) {
        tab->r[0] = tab->r[i];
        low = 1;
        high = i - 1;
        while (low <= high) {
            mid = (low + high) / 2;
            if (tab->r[0].key < tab->r[mid].key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        for (j = i - 1; j >= high + 1; j--) {
            tab->r[j + 1] = tab->r[j];
        }
        tab->r[high + 1] = tab->r[0];
    }
}


int main() {
    table tab;
    int i;
    keytype a[] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
    tab.length = sizeof(a) / sizeof(a[0]) - 1;
    for (i = 1; i <= tab.length; i++) {
        tab.r[i].key = a[i - 1];
    }
    binarysort(&tab);
    for (i = 1; i <= tab.length; i++) {
        printf("%d ", tab.r[i].key);
    }
    return 0;
}